1. Field of the Invention
The present invention relates to image encoding apparatus, image decoding apparatus and control method therefor.
2. Description of the Related Art
There are forms of entropy encoding used in image encoding that employ a static probability distribution model and those that use a dynamic model. Those using a static probability distribution model prepare a probability distribution model in advance by examining or postulating the nature of the information source, and perform suitable encoding for that model. Those using a dynamic probability distribution model learn the nature of the information source during the encoding process, and perform encoding while at the same time dynamically changing the probability distribution model.
Two examples of lossless coding of multivalued images are given here.
With a lossless coding system prescribed by JPEG and recommended by ISO and ITU-T as an international standard coding system for continuous-tone still images, a static model is used whereby encoding is performed using a Huffman table in which the differences between pixels of interest and predicted values are predetermined.
On the other hand, Part 1 of JPEG-LS recommended by ISO and ITU-T as an international standard system for lossless and near-lossless compression of continuous-tone still images is an exemplary dynamic model. JPEG-LS employs a Golomb encoding technique in prediction error coding, Golomb encoding being compatible with probability distributions that differ as a result of changing the encoding parameters. The probability distribution model is changed dynamically for every context determined from four pixels neighboring the pixel of interest, by selecting “k” with reference to the probability distribution condition of encoded symbols.
The overall flow of prediction error coding in JPEG-LS and a method for determining the Golomb encoding parameter will be described below. Note that in the following description, matters not directly related to the present invention, such as the run mode applied if pixels neighboring the pixel of interest all have the same pixel value or the quantization process for near-lossless coding, have been omitted. Reference should be made to the written standards for details on the standard system.
FIG. 3 shows the relative positional relation between the pixel of interest “x” and neighboring pixels a, b, c and d referred to by JPEG-LS. Attention is drawn to the fact that because the pixels are encoded in raster scan order, the pixels a, b, c and d neighboring the pixel of interest “x” have all been encoded. The values of the pixels are also expressed by a, b, c and d. Firstly, the differences between a and c, c and b, and b and d are derived to obtain D1, D2, and D3.D1=d−b D2=b−c D3=c−a 
The difference values D1, D2 and D3 are quantized in nine ways (from −4 to 4) to derive quantized values Q1, Q2 and Q3 of the respective differences. The correspondence of the range of the difference values and the quantized values are shown in FIG. 2. T1, T2 and T3 are predetermined non-negative integer values.
For example, the values T1=3, T2=7 and T3=21 are set in relation to 8-bit images that take values 0 to 255. 9×9×9=729 combinations (Q1, Q2, Q3) of Q1, Q2 and Q3 are thereby obtained, since it is possible for Q1, Q2 and Q3 to each have nine values from −4 to 4.
Here, the probability of the prediction error e occurring in the state (Q1, Q2, Q3) is considered the same as the probability of the prediction error −e occurring in the state (−Q1, −Q2, −Q3). Consequently, integrating these two states reduces the number of combinations to 365. Information showing this combination is the above context. An identifier expressing the 365 states is assumed to be S, and hereinafter this identifier S will be called a state number.
On the other hand, a predicted value p with respect to the value x of the pixel of interest is derived by the following equation using the neighboring pixels a, b and c.p=min(a,b) (if max(a,b))≦c) orp=max(a,b) (if min(a,b))≧c) orp=a+b−c (none of the above)
Here, min(x,y) is a function that returns the smaller of x and y, and max(x,y) is a function that returns the larger of x and y.
Attention is drawn to the fact that while the method of taking the predicted value p switches depending on the size relation of the values of the neighboring pixels a, b and c, the same predicted value p can be taken on the decoding side as the encoding side without needing to transmit additional information concerning the switch, since the pixels a, b and c have already been encoded. In order to improve predictive accuracy with JPEG-LS, a technique is used that involves correcting the predicted value p with reference to the mean value of the prediction errors produced up until that point with pixels encoded in state S, although description is omitted here.
The difference e between the predicted value p and the value x of the pixel of interest is derived, and the derived difference e is converted to a non-negative integer and Golomb encoded. At this time, an encoding parameter k is determined according to the context of the pixel of interest.
With JPEG-LS, an occurrence frequency N[S] for every state S, and an absolute sum A[S] of the prediction errors encoded in that state are held. The Golomb encoding parameter k satisfies the following condition using these two values. Note that “x^y”shows x to the power of y.2^(k−1)<A[S]/N[S]≦2^k 
In reality, the division A[S]/N[S] need not be performed. Deriving the smallest k such that N[S]×2^k≧A[S] is adequate. A large value will be thus selected for the k parameter when the absolute mean of the prediction errors is large, while a small k parameter will conversely be selected when the absolute mean of the prediction errors is small.
A[S] and N[S] are set to initial values at the start of encoding, and the probability distribution of each state is dynamically tracked by updating these values as required during the encoding process.
An image processing apparatus using the above JPEG-LS executes processing for determining the k parameter whenever a prediction error is encoded.
While measures such as making division unnecessary are taken to reduce the processing load, performing the processing that accompanies an indefinite number of decisions cannot be said to be efficient from the standpoint of processing load.
A large number of digits (bits) are required to hold the absolute sum of the prediction errors, and the memory capacity for A[S] can at times be problematic.
The encoding parameter k is determined based on the absolute mean of the prediction errors. Thus, the problem remains that when encoding an information source whose statistical nature changes greatly due, for example, to insufficient state separation, the occurrence of a large prediction error will cause an increase in the k parameter for the majority of prediction errors encoded thereinafter, for instance.